import java.util.PriorityQueue;

/**
 * Created by L.jp
 * Description:
 * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
 * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 *
 * 例如，[2,3,4]的中位数是 3
 *
 * [2,3] 的中位数是 (2 + 3) / 2 = 2.5
 *
 * 设计一个支持以下两种操作的数据结构：
 *
 * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 * double findMedian() - 返回目前所有元素的中位数。

 * User: 86189
 * Date: 2023-01-31
 * Time: 23:23
 */

/*
*  在大数据的规模下，我们使用传统的计算中位数的方法是不行的，这样时间复杂度太大了，我们必须使用最快的时间找到中位数
*  中位数一般是中间一个或者中间两个的平均数，怎样最快的找到中间一个和两个，那就是使用大小根堆，一个大根堆存储较小的一部分数那么较小的那一部分数的最大值就是堆顶
*   小根堆存储较大的那一部分数，那么较大的那部分数的最小值就是堆顶元素
*
* */
public class MedianFinder {
    PriorityQueue<Integer> max,min;
    public MedianFinder() {
        //把全部的数分为两部分，一部分为排序后的较小数值，一部分为排序后的较大数值，而大小根堆起到了排序的作用
        //大根堆，存储较小部分，堆顶是尾值
        max=new PriorityQueue<>((a,b)->(b-a));
        //小根堆，存储较大部分，堆顶是头值
        min=new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        if(min.size()>=max.size()){
            min.offer(num);
            max.offer(min.poll());
        }else {
            max.offer(num);
            min.offer(max.poll());
        }
    }
    
    public double findMedian() {
        if(min.size()>max.size()){
            return min.peek();
        }else if(max.size()>min.size()){
            return max.peek();
        }
        return (min.peek()+ max.peek())/2.0;
    }
}
